package ljl.alg.jianzhioffer.round3.easy;

import commons.ListNode;

import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class _52_getIntersectionNode {

    class use_map {

        ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null)
                return null;
            Set<ListNode> nodes = new HashSet<>();
            while (headA != null) {
                nodes.add(headA);
                headA = headA.next;
            }
            while (headB != null) {
                if (nodes.contains(headB))
                    return headB;
                headB = headB.next;
            }
            return null;
        }
    }

    class link_together {

        ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode a = headA;
            ListNode b = headB;
            while (a != b) {
                a = a == null ? headB : a.next;
                b = b == null ? headA : b.next;
            }
            return a;
        }
    }

    /**
     * 我了个去草！
     * */
    class why_wrong {

        ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode a = headA;
            ListNode b = headB;
            if (a == null || b == null)
                return null;
            while (a != b) {
                a = a.next;
                b = b.next;
                if (a == null)
                    a = headB;
                else if (b == null)
                    b = headA;
            }
            return a;
        }
    }

}

